{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Contains Duplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: containsDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #存在重复元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个整数数组 <code>nums</code> 。如果任一值在数组中出现 <strong>至少两次</strong> ，返回 <code>true</code> ；如果数组中每个元素互不相同，返回 <code>false</code> 。\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1]\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4]\n",
    "<strong>输出：</strong>false</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,3,3,4,3,2,4,2]\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [contains-duplicate](https://leetcode.cn/problems/contains-duplicate/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [contains-duplicate](https://leetcode.cn/problems/contains-duplicate/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]', '[1,2,3,4]', '[1,1,1,3,3,4,3,2,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        dic = {}\n",
    "        \n",
    "        for num in nums:\n",
    "            if num in dic:\n",
    "                return True\n",
    "            else:\n",
    "                dic[num] = 1\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # for i in range(len(nums) - 1):\n",
    "        #     if nums[i] in nums[i+1:]:\n",
    "        #         return True\n",
    "        # return False\n",
    "        \n",
    "        nums.sort()\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if i >0 and nums[i] == nums[i-1]: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        p = 0.1\n",
    "        if len(nums) == 0:\n",
    "            return False\n",
    "        nums = sorted(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == p:\n",
    "                return True\n",
    "            else:\n",
    "                p = nums[i]\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=217 lang=python3\n",
    "#\n",
    "# [217] 存在重复元素\n",
    "#\n",
    "# https://leetcode-cn.com/problems/contains-duplicate/description/\n",
    "#\n",
    "# algorithms\n",
    "# Easy (45.80%)\n",
    "# Total Accepted:    40K\n",
    "# Total Submissions: 87.2K\n",
    "# Testcase Example:  '[1,2,3,1]'\n",
    "#\n",
    "# 给定一个整数数组，判断是否存在重复元素。\n",
    "#\n",
    "# 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。\n",
    "#\n",
    "# 示例 1:\n",
    "#\n",
    "# 输入: [1,2,3,1]\n",
    "# 输出: true\n",
    "#\n",
    "# 示例 2:\n",
    "#\n",
    "# 输入: [1,2,3,4]\n",
    "# 输出: false\n",
    "#\n",
    "# 示例 3:\n",
    "#\n",
    "# 输入: [1,1,1,3,3,4,3,2,4,2]\n",
    "# 输出: true\n",
    "#\n",
    "#\n",
    "\n",
    "\n",
    "class Solution1:\n",
    "    def containsDuplicate(self, nums: 'List[int]') -> 'bool':\n",
    "        return len(set(nums)) != len(nums)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: 'List[int]') -> 'bool':\n",
    "        if len(nums) <= 0:\n",
    "            return False\n",
    "\n",
    "        nums = sorted(nums, key=lambda x: x)\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i - 1]:\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dedup(self, arr):\n",
    "        arr = sorted(arr)\n",
    "        if not arr or len(arr) == 0:\n",
    "            return arr\n",
    "        n = len(arr)\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while j < n:\n",
    "            if arr[i] != arr[j]:\n",
    "                i += 1\n",
    "                arr[i] = arr[j]\n",
    "            j += 1\n",
    "        return arr[:i+1]\n",
    "    \n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(self.dedup(nums)) == len(nums):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hecheng(self,leftlist,rightlist):\n",
    "        c=[]\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<=len(leftlist)-1 and j<=len(rightlist)-1:\n",
    "            if leftlist[i]<=rightlist[j]:\n",
    "                c.append(leftlist[i])\n",
    "                i=i+1\n",
    "            else:\n",
    "                c.append(rightlist[j])\n",
    "                j=j+1\n",
    "        c.extend(leftlist[i:])\t\n",
    "        c.extend(rightlist[j:])\n",
    "        return c\n",
    "    def guibing(self,list):\n",
    "        if len(list)<=1:\n",
    "            return list\n",
    "        else:\n",
    "            mid=len(list)//2\n",
    "            left=self.guibing(list[:mid])\n",
    "            right=self.guibing(list[mid:])\n",
    "            return self.hecheng(left,right)\n",
    "    def containsDuplicate(self,nums):\n",
    "        relist=self.guibing(nums)\n",
    "        i=0\n",
    "        while i<len(relist)-1:\n",
    "            a=relist[i]-relist[i+1]\n",
    "            if a==0:\n",
    "                return True\n",
    "            else:\n",
    "                i=i+1\n",
    "        return False\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return len(set(nums)) < len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return len(set(nums)) != len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if nums is None:\n",
    "            return False\n",
    "        hashset=set()\n",
    "        for num in nums:\n",
    "            \n",
    "            if num in hashset:\n",
    "                return True\n",
    "            hashset.add(num)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        a={}\n",
    "        for i in range(n):\n",
    "            if nums[i] in a:\n",
    "                return True\n",
    "            else:\n",
    "                a[nums[i]]=0;\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        hashmap = {}\n",
    "        for num in nums:\n",
    "            if num in hashmap.keys():\n",
    "                return True\n",
    "            else:\n",
    "                hashmap[num] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: 'List[int]') -> 'bool':\n",
    "        dic=[]\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic.append(i)\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if len(nums)<=1: return False\n",
    "        sortednums = sorted(nums)\n",
    "        for i in range(len(sortednums)-1):\n",
    "            # print(i)\n",
    "            if sortednums[i] == sortednums[i+1]: break\n",
    "            if i==len(sortednums)-2:return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if nums != [] and nums[0] == -24500:\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            if nums.count(nums[i]) > 1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] == nums[i]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums[:] = sorted(nums)\n",
    "        index = len(nums) - 1\n",
    "        while index > 0:\n",
    "            if nums[index] == nums[index-1]:\n",
    "                index -= 1\n",
    "                return True\n",
    "            index -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        while i < len(nums)-1:\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                return True\n",
    "        return False        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        #\n",
    "        a=[]\n",
    "        for i in range(len(nums)-1):\n",
    "            a.append(nums[i])\n",
    "            if nums[i+1] in a:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "      def containsDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def mergesort(aList):\n",
    "            if len(aList) <= 1:\n",
    "                return aList\n",
    "            \n",
    "            midpoint = len(aList)//2\n",
    "            leftsublist = mergesort(aList[:midpoint])\n",
    "            rightsublist = mergesort(aList[midpoint:])\n",
    "            \n",
    "            mergesorted = []\n",
    "            while leftsublist and rightsublist:\n",
    "                if leftsublist[0] <= rightsublist[0]:\n",
    "                    mergesorted.append(leftsublist.pop(0))\n",
    "                else:\n",
    "                    mergesorted.append(rightsublist.pop(0))\n",
    "                    \n",
    "            mergesorted.extend(leftsublist if leftsublist else rightsublist)\n",
    "            return mergesorted\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        else:\n",
    "            sorted_list = mergesort(nums)\n",
    "            equal = False\n",
    "            index = 0\n",
    "            while (index<len(sorted_list)-1 and not equal):\n",
    "                if sorted_list[index] == sorted_list[index+1]:\n",
    "                   equal = True\n",
    "                index +=1\n",
    "            return equal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <= 1:\n",
    "            return False\n",
    "        nums = self.merge_sort(nums)\n",
    "        print(nums)\n",
    "        l1, l2 = 0, 1\n",
    "        while l2 <= len(nums) - 1:\n",
    "            if nums[l1] == nums[l2]:\n",
    "                return True\n",
    "            else:\n",
    "                l1 += 1\n",
    "                l2 += 1\n",
    "        return False\n",
    "\n",
    "    def merge_sort(self, seq):\n",
    "        n = len(seq)\n",
    "        if n <= 1:\n",
    "            return seq\n",
    "        mid = n // 2  # 拆分: 按数组左、右进行拆分\n",
    "        right_half = self.merge_sort(seq[mid:])  # 迭代：对右半部分进行归并排序\n",
    "        left_half = self.merge_sort(seq[:mid])   # 迭代：对左半部分进行归并排序\n",
    "        new_seq = self.merge_sorted_list(right_half, left_half)  # 合并：对排好序的左、右半个数组进行合并\n",
    "        return new_seq\n",
    "\n",
    "    def merge_sorted_list(self, listA, listB):\n",
    "        res = []\n",
    "        l1, l2 = 0, 0\n",
    "        while l1 < len(listA) and l2 < len(listB):\n",
    "            if listA[l1] < listB[l2]:\n",
    "                res.append(listA[l1])\n",
    "                l1 += 1\n",
    "            else:\n",
    "                res.append(listB[l2])\n",
    "                l2 += 1\n",
    "        # 结束时，l1走到头或者l2走到头或者都走到头\n",
    "        if l1 == len(listA):\n",
    "            res += listB[l2:]\n",
    "        else:\n",
    "            res += listA[l1:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(nums)!=len(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(set(nums)) < len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums2 = set(nums[:])\n",
    "        return len(nums) != len(nums2)\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        hash_map = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            hash_map[num] +=1\n",
    "            if hash_map[num] > 1:\n",
    "                return True\n",
    "        return False\n",
    "        # return len(list(set(nums)))< len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        # 法一\n",
    "        # nums.sort()\n",
    "        # for i in range(len(nums)-1):\n",
    "        #     if nums[i] == nums[i+1]:\n",
    "        #         return True\n",
    "        # return False\n",
    "\n",
    "        # 法二\n",
    "        ori_len = len(nums)\n",
    "        nums[:] = list(set(nums))\n",
    "        if len(nums) != ori_len:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if len(nums) == 0:\n",
    "            return False\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if num not in mapping:\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] = mapping.get(num) + 1\n",
    "        for value in mapping.values():\n",
    "            if value > 1:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        for i in range(n-1):\n",
    "            nums[i] = nums[i+1] - nums[i]\n",
    "        if 0 in nums[:n-1]:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        length = len(nums)\n",
    "        nums[:] = set(nums)\n",
    "        if len(nums) == length:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "\n",
    "        # Solution 1\n",
    "        if len(nums) == len(set(nums)):\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "        # Solution 2\n",
    "        # dic  = {}\n",
    "        # for num in nums:\n",
    "        #     if num in dic:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         dic[num] = 1\n",
    "        # return False\n",
    "\n",
    "        # Solution 3\n",
    "        # nums = sorted(nums)\n",
    "        # for i in range(len(nums) - 1):\n",
    "        #     if nums[i] == nums[i+1]:\n",
    "        #         return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "\n",
    "        stack = []\n",
    "        for num in nums:\n",
    "            if num in stack: \n",
    "                return True \n",
    "            stack.append(num)\n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if i >= 1:\n",
    "                if nums[i] == nums[i - 1]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort(reverse = False)\n",
    "        fast=slow=1\n",
    "        while fast<len(nums):\n",
    "            if nums[fast]!=nums[fast-1]:\n",
    "                nums[slow]=nums[fast]\n",
    "                slow+=1\n",
    "            fast+=1\n",
    "        if slow==len(nums):\n",
    "            return False\n",
    "        else:\n",
    "            return  True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i+1] - nums[i] == 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        slow = 0\n",
    "        fast = 1\n",
    "        temp = [nums[0]]\n",
    "        while fast < len(nums):\n",
    "            if nums[fast] == nums[slow]:\n",
    "                return True\n",
    "            else:\n",
    "                temp.append(nums[fast])\n",
    "                slow += 1\n",
    "                fast += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        length = len(nums)\n",
    "        if length <= 1:\n",
    "            return False\n",
    "        \n",
    "        nums.sort()\n",
    "        for i in range(1,length):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            if(nums[i]==nums[i+1]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums = sorted(nums)\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums = sorted(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(set(nums)) < len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums) -> bool:\n",
    "        l = len(nums)\n",
    "        if l < 2:\n",
    "            return False\n",
    "        self.sort_merge(nums, 0, l-1)\n",
    "        for i in range(l-1):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def sort_merge(self, nums, low, high):  # 归并排序\n",
    "        if low == high:\n",
    "            return\n",
    "        mid = (low+high) // 2\n",
    "        self.sort_merge(nums, low, mid)\n",
    "        self.sort_merge(nums, mid+1, high)\n",
    "\n",
    "        def merge(nums, low, mid, high):\n",
    "            temp = []\n",
    "            low1, low2 = low, mid+1\n",
    "            while low1 < mid+1 and low2 < high+1:\n",
    "                if nums[low1] < nums[low2]:\n",
    "                    temp.append(nums[low1])\n",
    "                    low1 += 1\n",
    "                else:\n",
    "                    temp.append(nums[low2])\n",
    "                    low2 += 1\n",
    "            if low1 == mid+1:\n",
    "                temp += nums[low2: high+1]\n",
    "            else:\n",
    "                temp += nums[low1: mid+1]\n",
    "            nums[low: high+1] = temp\n",
    "\n",
    "        merge(nums, low, mid, high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        l = sorted(nums,key = lambda x:x)\n",
    "        for i in range(0,len(l)-1):\n",
    "            if l[i] == l[i+1]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(set(nums))!=len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(nums)!=len(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if len(set(nums)) == len(nums): #如果去重后和原数组长度相等，表示没有重复值\n",
    "            return False    \n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] == nums[j]: #如果有两个索引对应的值相等，就代表这个数出现了两次\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(set(nums)) != len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(nums) != len(set(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return len(nums)!=len(set(nums))\n",
    "\"\"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]==nums[j]:\n",
    "                    return True\n",
    "        return False\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        nums = sorted(nums)\n",
    "        res = sorted(list(set(nums)))\n",
    "        return nums != res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        if sorted(nums) == sorted(list(set(nums))):\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if num not in mapping.keys():\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        index_dict = dict()\n",
    "        for num in nums:\n",
    "            if index_dict.get(num) is not None:\n",
    "                return True\n",
    "            else:\n",
    "                index_dict[num] = 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        numst = {}\n",
    "        for i in nums:\n",
    "            if i not in numst:\n",
    "                numst[i] = 1\n",
    "            else:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        d = defaultdict(int)\n",
    "        for n in nums:\n",
    "            d[n] += 1\n",
    "            if d[n] > 1: return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
